package org.hot100_0.leetcode146;

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    class LRUCache {

        class Node {
            int key;
            int val;

            Node pre;
            Node next;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }

        }

        int capacity;

        HashMap<Integer, Node> hashMap = new HashMap<>();

        Node dummy;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            dummy = new Node(-1, -1);
            dummy.next = dummy;
            dummy.pre = dummy;
        }

        public int get(int key) {
            Node node = getNode(key);
            if (node == null) {
                return -1;
            }
            return node.val;
        }

        public void put(int key, int value) {
            Node node = getNode(key);

            if (node != null) {
                node.val = value;
            } else {
                Node newNode = new Node(key, value);
                hashMap.put(key, newNode);
                putHead(newNode);
                if (hashMap.size() > capacity) {
                    hashMap.remove(dummy.pre.key);
                    deleteNode(dummy.pre);
                }
            }
        }

        private Node getNode(int key) {
            Node node = hashMap.get(key);
            if (node != null) {
                deleteNode(node);
                putHead(node);
            }
            return node;
        }

        private void putHead(Node node) {
            dummy.next.pre = node;
            node.next = dummy.next;

            dummy.next = node;
            node.pre = dummy;
        }

        private void deleteNode(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

    }
}
